#ifndef MGRAPH_H
#define MGRAPH_H
#include "GraphKind.h"
#include "functional"
#include <QQueue>
#include <functional>
using namespace std;
typedef int VRType;
typedef const char *InfoType;
namespace MyGraph {
#define NOT_FOUND -1
};
template <typename T>
class MGraph
{
public:
    #define INDEX(x,w) (x*MAX_VERTEX_NUM+w)
    typedef class ArcCell{
    public:
        VRType adj;//代表连通性
        InfoType info;//附加信息
        ArcCell(VRType adj=0,InfoType info=nullptr):adj(adj),info(info){}
    };
    MGraph(GraphKind kind=DN,int MAX_VERTEX_NUM=10):kind(kind),MAX_VERTEX_NUM(MAX_VERTEX_NUM){
        arcs=new ArcCell[MAX_VERTEX_NUM*MAX_VERTEX_NUM];
        vexs=new T[MAX_VERTEX_NUM];
        vexnum=0;
        arcnum=0;
    }
    void InsertVex(T data){
        if(vexnum<MAX_VERTEX_NUM){
            vexs[vexnum++]=data;
        }else{
            throw "顶点添加失败!";
        }
    }
    // bool DeleteVex(T data){
    //     for(int i=0;i<vexnum;i++){
    //         if(data==vexs[i]){
    //             return
    //         }
    //     }
    // }
    int Locate(T data){
        for(int i=0;i<MAX_VERTEX_NUM;i++){
            if(data==vexs[i]){
                return i;
            }
        }
        return NOT_FOUND;
    }
    bool InsertArc(T v,T w,const char *msg=nullptr){
        int from=Locate(v);
        int to=Locate(w);
        if(from==NOT_FOUND||to==NOT_FOUND||from==to){
            return false;
        }
        arcs[INDEX(from,to)].adj=1;
        if(kind==UDN||kind==UDG){
            arcs[INDEX(to,from)].adj=1;
            arcs[INDEX(to,from)].info=msg;
        }
        if(msg){
            arcs[INDEX(from,to)].info=msg;

        }
        arcnum++;
        return true;
    }
    bool DeleteArc(T v,T w){
        int from=Locate(v);
        int to=Locate(w);

        if(from==NOT_FOUND||to==NOT_FOUND||from==to){
            return false;
        }
        if(arcs[INDEX(to,from)].adj){
            arcnum--;
        }
        if(kind==UDN||kind==UDG){
            arcs[INDEX(to,from)]=0;
        }
        arcs[INDEX(from,to)]=0;


        return true;
    }
    void ReSetValue(T v,T newvalue){
        vexs[Locate(v)]=newvalue;
    }
    void TraverseVex(function<void(T)> func){
        for(int i=0;i<vexnum;i++){
            func(vexs[i]);
        }
    }
    void TraverseArc(function<void(int from,int to,ArcCell &cell)> func){
        for(int i=0;i<vexnum;i++){
            for(int j=0;j<vexnum;j++){
                func(i,j,arcs[INDEX(i,j)]);
            }
        }
    }
    bool repeat(T data){
        for(int i=0;i<vexnum;i++){
            if(vexs[i]==data){
                return true;
            }
        }
        return false;
    }
    int GetVexCount(){
        return vexnum;
    }
    void DFSTraverse(std::function<void(int,string)>func){
        bool *visited=new bool[vexnum];
        for(int i=0;i<vexnum;i++){
            DFS(i,func,visited);
        }

    }
    void DFS(int index,std::function<void(int,string)>func,bool *visited){
        if(visited[index]==false){
            visited[index]=true;
            func(index,vexs[index]);
            for(auto i=FirstAdjvex(index);i!=NOT_FOUND;i=NextAdjvex(index,i)){
                if(visited[i]==false){
                    DFS(i,func,visited);
                }
            }
        }
    }
    void BFSTraverse(std::function<void(int,string)>func){
        bool *visited=new bool[vexnum];
        QQueue<int> q;

        for(int i=0;i<vexnum;i++){
            if(!visited[i]){
                visited[i]=true;
                func(i,vexs[i]);
                q.enqueue(i);
            }
            while(!q.empty()){
                auto temp=q.dequeue();
                for(int i=FirstAdjvex(temp);i!=NOT_FOUND;i=NextAdjvex(temp,i)){
                    if(!visited[i]){
                        visited[i]=true;
                        func(i,vexs[i]);
                        q.enqueue(i);
                    }
                }
            }
        }
    }
    int FirstAdjvex(int index){
        for(int i=0;i<vexnum;i++){
            if(arcs[INDEX(index,i)].adj){
                return i;
            }
        }
        return NOT_FOUND;
    }
    int NextAdjvex(int index,int pre){
        for(int i=pre+1;i<vexnum;i++){
            if(arcs[INDEX(index,i)].adj){
                return i;
            }
        }
        return NOT_FOUND;
    }
    int MAX_VERTEX_NUM=10;
    ArcCell *arcs;
    T *vexs;
    int vexnum,arcnum;
    GraphKind kind;
};

#endif // MGRAPH_H
